package lanqiao._02算法训练.page02;

import java.util.*;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 问题描述
 * 　　逗志芃励志要成为强力党，所以他将身上所以的技能点都洗掉了重新学技能。现在我们可以了解到，
 * 每个技能都有一个前提技能，只有学完了前提技能才能学习当前的技能（有一个最根本的技能不需要前提技能）。
 * 学习每个技能要消耗一个技能点，然后可以获得这个技能的威力值。由于逗志芃要陪妹子，
 * 所以他希望你教他如何点技能使得威力值最大从而成为强力党。
 * 输入格式
 * 　　第一行两个数n，m表示有n个技能和m个技能点。第二行有n个数，第i个数表示第i个技能的威力值。
 * 　　之后的n-1行，每行两个数x,y，表示y技能的前提技能是x，也就是说先学第x个技能才能学弟y个技能。
 * 输出格式
 * 　　一个数，最大的威力值。
 * 样例输入
 * 3 2
 * 1 10 20
 * 1 2
 * 1 3
 * 样例输出
 * 21
 * 数据规模和约定
 * 　　0<n,m<=200, 技能的威力值不超过200。
 * @since 2022 - 11 - 09 - 18:10
 */
public class _18强力党逗志芃 {
}

/* 每一个技能都有一个且只有一个前提技能，且只有一个没有前提技能的，
 * 所以一定有且只有一个树根， 且每一个点有且只有一个入度。
 * 所以构成一个有向树。
 *
 * 还需要计算出每一层的最大值
 * 总和为m,分配个k个结点，每一个结点如果有t个值，会有不同的结果。
 * 然后需要求出将m分配给k个结点的最大值。
 *
 * 典型的分组背包问题，每一个结点是一个组，每个组中有体积不同的值，每个组中的
 * 物品最多选择一个。
 *
 * 分成n个组，dp[i][j]表示第j个物品的价值，j表示第j个物品的体积。
 * 背包的容量是变化的
 *
 *
 *
 */
class Main18_2 {
    //物品数 背包容量
    static int n, m;
    //物品价值
    static int[] values;
    //邻接表
    static Map<Integer, List<Integer>> graph;
    //dp[i][j] : 以i为根 背包j能取得最大价值
    static int[][] dp;

    static void dfs(int root) {
        //可选root
        for (int j = 1; j <= m; j++) dp[root][j] = values[root];
        for (int child : graph.get(root)) {
            dfs(child);
            //枚举背包体积
            for (int j = m; j >= 1; j--) {
                //分给子节点
                for (int k = 0; k <= j - 1; k++) {
                    dp[root][j] = Math.max(dp[root][j], dp[root][j - k] + dp[child][k]);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        values = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            values[i] = sc.nextInt();
        }
        graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new LinkedList<>());
        }
        int a, b;
        //入度
        int[] inDegrees = new int[n + 1];
        int root = 1;
        for (int i = 1; i < n; i++) {
            a = sc.nextInt();
            b = sc.nextInt();
            graph.get(a).add(b);
            inDegrees[b]++;
        }
        //找根节点
        for (int i = 1; i < n; i++) {
            if (inDegrees[i] == 0) {
                root = i;
                break;
            }
        }
        dp = new int[n + 1][m + 1];
        dfs(root);
        System.out.println(dp[root][m]);
    }
}

class Main18 {
    private static int n, m;
    //邻接矩阵
    private static Map<Integer, List<Integer>> graph;
    //入度
    static int[] inDegrees;
    private static int[] nums;
    //dp[i][j] : 以节点i为根的树中取j个节点得到的最大值
    public static int[][] dp;

    // 对于结点u为根的树，有m个可以选择的点的最大值, 并且一定要选择u
    public static void dfs(int u) {
        for (int next : graph.get(u)) {
            dfs(next);
            // 枚举技能点 [0, m - 1]
            for (int i = m - 1; i >= 0; i--) {
                // 给next 子节点分j 个技能点
                for (int j = 0; j <= i; j++) {
                    dp[u][i] = Math.max(dp[u][i], dp[u][i - j] + dp[next][j]);
                }
            }
        }
        // 当前结点必选，所以dp[u][i]应该是子节点中选择i - 1个，然后加上自己
        // 注意是逆序，正序就成了求前缀和了
        for (int i = m; i >= 1; i--) dp[u][i] = dp[u][i - 1] + nums[u];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dp = new int[n][m + 1];
        inDegrees = new int[n];
        Arrays.fill(inDegrees, 0);
        graph = new HashMap<>();
        nums = new int[n];
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
            Arrays.fill(dp[i], 0);
            nums[i] = sc.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            //输入的节点编号从1开始，我们从0开始
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            graph.get(a).add(b);
            inDegrees[b]++;
        }
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (inDegrees[i] == 0) {
                root = i;
                break;
            }
        }
        dfs(root);
        System.out.println(dp[root][m]);
    }
}

//dfs 不正确且超时
class Main18_1 {
    static int n, m;
    static int[] nums;
    static int[] inDegrees = new int[205];
    static Map<Integer, List<Integer>> graph;
    static int max = 0;
    static boolean[] vis = new boolean[205];

    static void dfs(int cnt, int pre, int cur, int sum) {
        if (cnt == 0) {
            max = Math.max(max, sum);
            return;
        }
        vis[cur] = true;
        List<Integer> nextList = graph.get(cur);
        for (int next : nextList) {
            inDegrees[next]--;
        }

        //选同层
        for (int bro : graph.get(pre)) {
            if (!vis[bro]) {
                vis[bro] = true;
                dfs(cnt - 1, pre, bro, sum + nums[bro]);
                vis[bro] = false;
            }
        }
        //选后面的
        for (int next : nextList) {
            if (!vis[next] && inDegrees[next] <= 0) {
                vis[next] = true;
                dfs(cnt - 1, cur, next, sum + nums[next]);
                vis[next] = false;
            }
        }

        for (int next : nextList) {
            inDegrees[next]++;
        }
        vis[cur] = false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        nums = new int[n + 1];
        graph = new HashMap<>();
        max = 0;
        //注意从1开始
        for (int i = 1; i <= n; i++) {
            graph.put(i, new LinkedList<>());
        }
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
        //建图
        int a, b;
        for (int i = 0; i < n - 1; i++) {
            a = sc.nextInt();
            b = sc.nextInt();
            graph.get(a).add(b);
            inDegrees[b]++;
        }
        //找入度为0的(最基础的技能)
        int p = 1;
        for (int i = 1; i <= n; i++) {
            if (inDegrees[i] == 0) {
                p = i;
                break;
            }
        }
        dfs(m - 1, p, p, nums[p]);
        System.out.println(max);
    }
}